package com.ai.zuochengyun.phase01.class05;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 动态并查集  可以查找与合并的一种数据结构
 */
public class Code04_NumberOfIslandsII {

    public static List<Integer> numIslands1(int m, int n, int[][] positions) {
        List<Integer> ans = new ArrayList<>();
        UnionFind1 uf = new UnionFind1(m, n);
        for (int[] pos : positions) {
            ans.add(uf.connect(pos[0], pos[1]));
        }
        return ans;
    }

    public static class UnionFind1 {
        private final int[] parent;

        private final int[] size;

        private final int[] help;

        private final int row;

        private final int col;

        private int sets;

        public UnionFind1(int row, int col) {
            this.row = row;
            this.col = col;
            int len = row * col;
            parent = new int[len];
            size = new int[len];
            help = new int[len];
        }

        /**
         * 二维数组中某一个位置来了一个1
         *
         * @param r
         * @param c
         * @return
         */
        private int connect(int r, int c) {
            // 通过行列，换算成一维数组的下标
            int index = index(r, c);

            // 如果有1，代表之前该位置已经初始化过了，就不做任何处理
            if (size[index] == 0) {
                // 你自己的父节点是你自己
                parent[index] = index;
                // 你的集合的大小是1
                size[index] = 1;
                // 集合的数量++
                sets++;

                // 看下当前位置上下左右是否可以合并
                union(r - 1, c, r, c);
                union(r + 1, c, r, c);
                union(r, c - 1, r, c);
                union(r, c + 1, r, c);
            }
            return sets;
        }

        /**
         * 合并
         *
         * @param r1
         * @param c1
         * @param r2
         * @param c2
         */
        private void union(int r1, int c1, int r2, int c2) {
            // 判断位置是否越界
            if (r1 < 0 || r1 >= row || c1 < 0 || c1 >= col) {
                return;
            }
            if (r2 < 0 || r2 >= row || c2 < 0 || c2 >= col) {
                return;
            }
            // 换算坐标
            int i1 = index(r1, c1);
            int i2 = index(r2, c2);
            // 如果两者不同时为1，就不参与合并
            if (size[i1] != 1 || size[i2] != 1) {
                return;
            }

            // 找到当前位置对应的代表节点
            int head1 = find(i1);
            int head2 = find(i2);
            // 如果两者的代表节点不一样，那么就开始合并
            if (head1 != head2) {
                // 将小的挂到大的下面
                if (size[head1] >= size[head2]) {
                    size[head1] += size[head2];
                    parent[head2] = head1;
                } else {
                    size[head2] += size[head1];
                    parent[head1] = head2;
                }
                sets--;
            }
        }

        private int find(int loc) {
            int helpIndex = 0;
            // 一直向上找，直到找到最开始的代表节点
            while (loc != parent[loc]) {
                help[helpIndex++] = loc;
                loc = parent[loc];
            }

            // 通过记录的沿途的节点，将数据扁平化
            for (helpIndex--; helpIndex >= 0; helpIndex--) {
                parent[help[helpIndex]] = loc;
            }
            return loc;
        }

        private int index(int r, int c) {
            return r * col + c;
        }
    }

    /**
     * 不初始化数组的方式，如果m和n很大，会经历很重的初始化，而k比较小的时候的优化方案
     *
     * @param m
     * @param n
     * @param positions
     * @return
     */
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> ans = new ArrayList<>();
        UnionFind2 uf = new UnionFind2();
        for (int[] pos : positions) {
            ans.add(uf.connect(pos[0], pos[1]));
        }
        return ans;
    }

    private static class UnionFind2 {
        public Map<String, String> parentMap;

        public Map<String, Integer> sizeMap;

        public List<String> help;

        public int sets;

        public UnionFind2() {
            this.parentMap = new HashMap<>();
            this.sizeMap = new HashMap<>();
            this.help = new ArrayList<>();
            sets = 0;
        }

        public int connect(int row, int cel) {
            String loc = row + "_" + cel;
            if (!parentMap.containsKey(loc)) {
                // 自己的父亲是自己
                parentMap.put(loc, loc);
                // 自己集合的大小设为1
                sizeMap.put(loc, 1);
                sets++;

                // 看下当前位置上下左右是否可以合并
                String locUp = (row - 1) + "_" + cel;
                String locDown = (row + 1) + "_" + cel;
                String locLeft = row + "_" + (cel - 1);
                String locRight = row + "_" + (cel + 1);

                union(loc, locUp);
                union(loc, locDown);
                union(loc, locLeft);
                union(loc, locRight);
            }
            return sets;
        }

        /**
         * 查找
         * @param loc
         * @return
         */
        public String find(String loc) {
            while (!loc.equals(parentMap.get(loc))) {
                help.add(loc);
                loc = parentMap.get(loc);
            }


            for (String s : help) {
                parentMap.put(s, loc);
            }
            help.clear();
            return loc;
        }

        /**
         * 合并
         * @param loc
         * @param otherLoc
         */
        public void union(String loc, String otherLoc) {
            if (!parentMap.containsKey(loc) || !parentMap.containsKey(otherLoc)) {
                return;
            }
            String head1 = find(loc);
            String head2 = find(otherLoc);
            if (!head1.equals(head2)) {
                int size1 = sizeMap.get(head1);
                int size2 = sizeMap.get(head2);
                if (size1 >= size2) {
                    sizeMap.put(head1, size1 + size2);
                    parentMap.put(head2, head1);
                } else {
                    sizeMap.put(head2, size2 + size1);
                    parentMap.put(head1, head2);
                }
                sets--;
            }
        }

        public int size() {
            return sets;
        }
    }
}
